#ifndef _JOIN_MERGE_HPP
#define _JOIN_MERGE_HPP

#include "stopwatch.hpp"

#include <algorithm>
#include <vector>


/*
 * Perform merge join intersection algorithm.
 */
template <typename T>
void mergeJoin(std::vector<T> &set1, std::vector<T> &set2, std::vector<T> &res)
{
//	Stopwatch stopwatch(true);
	std::sort(set1.begin(), set1.end());
	std::sort(set2.begin(), set2.end());
//	stopwatch.stop();
//	std::cout << "Sorting took " << stopwatch.getMiliseconds() << "ms" << std::endl;

	unsigned i1 = 0, i2 = 0;
	while (i1 < set1.size() && i2 < set2.size()) {
		if (set1[i1] == set2[i2]) {
			res.push_back(set1[i1]);
			++i1; ++i2;
		} else {
			if (set1[i1] < set2[i2]) ++i1; else ++i2;
		}
	}
}


#endif
